/**
 * @param {arr: array 原数组数组, id: number 父节点id} 
 * @return {children: array 子数组}
 */
function getChildren(arr, id) {
	const res = [];
	for (const item of arr) {
		if (item.pid === id) {
			// 找到当前id的子元素
			// 插入子元素，每个子元素的children通过回调生成
			res.push({ ...item, children: getChildren(arr, item.id) });
		}
	}
	return res;
}

const arr = [
	{ id: 1, name: '部门1', pid: 0 },
	{ id: 2, name: '部门2', pid: 0 },
	{ id: 3, name: '部门3', pid: 1 },
	{ id: 4, name: '部门4', pid: 3 },
	{ id: 5, name: '部门5', pid: 4 }
];

const obj = {
	id: 1,
	name: '部门1',
	pid: 0,
	children: [
		{
			id: 2,
			name: '部门2',
			pid: 1,
			children: []
		},
		{
			id: 3,
			name: '部门3',
			pid: 1,
			children: [
				{
					id: 4,
					name: '部门4',
					pid: 3,
					children: [
						{
							id: 5,
							name: '部门5',
							pid: 4,
							children: []
						}
					]
				}
			]
		}
	]
};

/**
 * @param {arr: array, pid: number}
 * @return {obj: object}
 */
function fn(arr, pid) {
	const map = new Map(); // 生成map存储元素
	for (const item of arr) {
		if (!map.has(item.id)) {
			// 若map中没有当前元素，添加并初始化children
			map.set(item.id, { ...item, children: [] });
		} else {
			// 若不存在父元素 pid，后续会构造一个空的父元素，就会出现当前元素 item 已经存在的情况；此时需要将当前元素与已存在的元素（创建的父元素）进行合并
			map.set(item.id, { ...map.get(item.id), ...item });
		}
		if (map.has(item.pid)) {
			// 查找父元素，存在则将该元素插入到children
			map.get(item.pid).children.push(map.get(item.id));
		} else {
			// 否则初始化父元素，并插入children
			map.set(item.pid, { children: [ map.get(item.id) ] });
		}
	}
	return map.get(pid);
}

console.log(fn(arr, 0));

console.log(getChildren(arr, 0));

/**
 * @param {obj: object, res: array}
 * @return {arr: array}
 */
function fn2(obj, res = []) {
	// 默认初始结果数组为[]
	res.push(obj); // 当前元素入栈
	// 若元素包含children，则遍历children并递归调用使每一个子元素入栈
	if (obj.children && obj.children.length) {
		for (const item of obj.children) {
			fn2(item, res);
		}
	}
	return res;
}

console.log(fn2(obj));
